package com.weirn.algorithm.linkedlist;

import java.util.*;

/**
 * 双链表操作,支持null元素.di第一个元素就是实体元素没有头元素
 * 非线程安全
 * Created by yp-tc-2563 on 2018/1/25.
 */
public class DoubleLinkedList<E> implements List<E>{

    private int size;

    private Node head;

    private Node last;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf ( 0 ) == -1;
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr ();
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }

    @Override
    public boolean add(E e) {
        Node<E> node = new Node<> ( e);
        if(head == null){
            head = node;
            last = node;
        }else{
            node.previous = last;
            node.next = null;
            last.next = node;
            last = node;
        }
        size++;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if(o ==null){
            for(Node e = head;e != null; e = e.next){
                if(o == e.object ){
                    unlink ( e );
                    return true;
                }
            }
        }else{
            for(Node e = head;e != null; e = e.next){
                if(o.equals ( e.object )){
                    unlink ( e );
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public void clear() {

    }

    @Override
    public E get(int index) {
        checkElementIndex ( index );
        return node ( index ).object;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public void add(int index, E element) {

    }

    @Override
    public E remove(int index) {
        E removeE = null;
        checkElementIndex ( index );
        removeE = unlink ( node ( index ) );
        return removeE;
    }

    private Node<E> node(int index){
        if(index <= size/2){
            Node<E> x = this.head;
            //因为第一个元素为实体元素,非空元素,所以遍历从1开始,如果第一个元素为头元素(虚元素),则从0开始
            for(int i = 1;i < index;i++,x = x.next){
//                x = x.next;
            }
            return x;
        }else{
            Node<E> x = this.last;
            for(int i = size; i > index; i--,x = x.previous){
//                x = x.previous;
            }
            return x;
        }
    }

    private void checkElementIndex(int index){
        if(!isElementIndex ( index ))
            throw new IndexOutOfBoundsException ( outBoundMsg ( index ) );
    }

    private String outBoundMsg(int index){
        return "Index" + index + ",Size" + size ();
    }

    private boolean isElementIndex(int index){
        return index > 0 && index <= size ();
    }

    @Override
    public int indexOf(Object o) {
        int index = 0;
        if(o == null){
            for(Node<E> e = head;e == null;e = e.next){
                if(e.object == null){
                    return index;
                }
                index ++;
            }
        }else{
            for(Node<E> e = head;e == null;e = e.next){
                if(o.equals ( e.object )){
                    return index;
                }
                index++;
            }
        }

        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public ListIterator<E> listIterator() {
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return null;
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        return null;
    }

    /**
     * e 非空元素
     * @param e
     * @return
     */
    public E unlink(Node<E> e){
       E element = e.object;
       Node<E> previous = e.previous;
       Node<E> next = e.next;

       if(previous == null){
           head = next;
       }else{
           previous.next = next;
           e.previous = null;
       }
       if ( next == null ){
           last = previous;
       }else{
           next.previous = previous;
           e.next = null;
       }

       e.object = null;
       size--;

        return element;
    }

    public void reverseDisplay(){
        if(size == 0){
            System.out.println ("Empty!");
        }
        int i = 0;
        for(Node<E> e = last; e != null; e = e.previous){
            System.out.print("(值:"+e.object+",序号:"+(i++)+")<--");
        }
        System.out.println();
    }

    public void display(){
        if(size == 0){
            System.out.println ("Empty!");
            return;
        }
        int i=0;
        for(Node<E> e = head;e != null ;e = e.next){
            System.out.print("(值:"+e.object+",序号:"+(i++)+")-->");
        }
        System.out.println();
    }

    private class Node<E>{
        private E object;
        private Node previous; //before
        private Node next; //after

        public Node(Node previous,E e,Node next) {
            this.previous = previous;
            this.object = e;
            this.next = next;
        }

        public Node(E object) {
            this.object = object;
        }

        public E getObject() {
            return object;
        }

        public void setObject(E object) {
            this.object = object;
        }

        public Node getPrevious() {
            return previous;
        }

        public void setPrevious(Node previous) {
            this.previous = previous;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    private class Itr implements Iterator<E>{

        int cursor = 1;

        int lastCUR = 0;


        @Override
        public boolean hasNext() {
            return cursor <= size;
        }

        @Override
        public E next() {
            try {
                int i = cursor;
                lastCUR = i;
                E next = get ( i );
                cursor = i + 1;
                return next;
            } catch ( Exception e ){
                e.printStackTrace ();
            }
            return null;
        }
    }

    public static void main(String args[]){
        LinkedList<String> linkedList = new LinkedList<String> ( );

        DoubleLinkedList<String> doubleLinkedList = new DoubleLinkedList<> ();
        doubleLinkedList.add ( "1" );
        doubleLinkedList.add ( "2" );
        doubleLinkedList.add ( "3" );
        doubleLinkedList.add ( "4" );
        doubleLinkedList.add ( null );
        doubleLinkedList.display ();
        doubleLinkedList.reverseDisplay();
        doubleLinkedList.add ( "5" );
        doubleLinkedList.add ( "6" );
        doubleLinkedList.display ();
        doubleLinkedList.reverseDisplay();
        System.out.println ("================="+doubleLinkedList.node ( 1 ).object);
        System.out.println ("================="+doubleLinkedList.node ( 2 ).object);
        System.out.println ("================="+doubleLinkedList.node ( 7 ).object);
        doubleLinkedList.remove ( "4" );
        doubleLinkedList.remove ( 4 );
        doubleLinkedList.remove ( "1" );
        doubleLinkedList.remove ( null );
        doubleLinkedList.display ();
        doubleLinkedList.reverseDisplay();
        System.out.println ("=================");
        Iterator<String> itr = doubleLinkedList.iterator ();
        while(itr.hasNext ()){
            System.out.println (itr.next ());
        }
    }
}
